package Recursive_search_backtracking_algorithm.Topic1_recursive_algorithm.Topic1_recursive_algorithm;

public class swap_nodes_in_pairs {
    //24. 两两交换链表中的节点
    //https://leetcode.cn/problems/swap-nodes-in-pairs/description/
    public Topic1_recursive_algorithm.ListNode swapPairs(Topic1_recursive_algorithm.ListNode head) {
        if(head==null||head.next==null){  //没有节点或者只剩一个节点，就不需要交换，直接返回（易错点一）
            return head;
        }
        //牢记 dfs() 的任务：1. 把第三个节点之后的链表节点两两交换；2. 返回交换后的头节点(这两点自己想都不好想，尤其是第二点)

        Topic1_recursive_algorithm.ListNode tmp = swapPairs(head.next.next);  //先用 dfs 交换除前面两个节点之外的其他节点，也就是第三个节点（易错点二）

        Topic1_recursive_algorithm.ListNode ret = head.next;    //需要记录原链表的第二个节点作为返回值（易错点三）

        ret.next=head;   //子问题：交换两个节点，并且拿交换部分和经过 dfs 得到的链表头节点连接

        head.next=tmp;

        return ret;   //原链表第二个节点
    }
}
